% Version control information:
%\svnid{$Id: fuerza_bruta.tex 5 2009-03-29 23:59:23Z asalber $
%
\section{Técnicas Algorítmicas}

%---------------------------------------------------------------------slide----
\begin{frame}
  \frametitle{Técnicas Algorítmicas}
  \tableofcontents[sectionstyle=show/hide,hideothersubsections]
\end{frame}

\subsection{Fuerza bruta}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Técnicas de resolución de problemas}
\begin{itemize}
\item En el tema anterior vimos que no todos los algoritmos son igual de eficientes para resolver un problema.
\begin{center}
\alert{¿Cómo construir algoritmos eficientes?}
\end{center}
\item En este tema veremos una serie de técnicas que permiten construir algoritmos eficientes dependiendo del tipo de problema que se quiera resolver:
\begin{itemize}
\item Fuerza bruta
\item Divide y vencerás (divide and conquer)
\item Técnica voraz (greedy)
\item Programación dinámica (dynamic programming)
\item Vuelta atrás (backtracking)
\item Ramificación y poda (branch \& bound)
\item Técnicas probabilistas
\end{itemize}
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Técnica de fuerza bruta}
\begin{itemize}
\item La técnica de \textbf{fuerza bruta} es la que se utiliza para resolver un problema siguiendo la estrategia más obvia (y seguramente más rudimentaria) de solución.

\item Generalmente suele comportar más operaciones de las necesarias para resolver el problema, por lo suelen tener un coste bastante alto.

\item Por el contrario, suele ser bastante sencilla de implementar.

\item Suelen utilizarse para problemas de tamaños pequeños, donde el coste asintótico no importa.

\item Algunos ejemplos de algoritmos por fuerza bruta son:
\begin{itemize}
\item El algoritmo de búsqueda lineal.
\item El algoritmo ordenación por el método de selección o inserción.
\end{itemize}
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Búsqued lineal}
\framesubtitle{Ejemplo de fuerza bruta}
\begin{itemize}
\item La siguiente función en Java realiza una búsqueda lineal de un entero en un vector de enteros:
\begin{lstlisting}
// BusquedaLineal.java
public static int busquedaLineal(int[] a, int x){
  for (int i = 0; i < a.length; i++)
    if (a[i]==x) return i;
  return -1;
}
\end{lstlisting}

\item El algoritmo utiliza la fuerza bruta para buscar el número mirando uno por uno todos los elementos del vector, incluso si el vector estuviese ordenado.

\item Vimos que el coste de este algoritmo es $O(n)$.

\item Aunque no es la forma óptima de buscar un elemento en un vector ordenado, cuando el tamaño del vector es pequeño resulta bastante rápido.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Ordenación de un vector por inserción}
\framesubtitle{Ejemplo de fuerza bruta}
La siguiente función en Java ordena un vector de enteros mediante la técnica de inserción.
\begin{lstlisting}
// OrdenacionInsercion.java
public static void ordenacionInsercion(int[] a){
  for(int i=1; i<a.length; i++){
    int aux=a[i];
    int j = i;
    while ((j > 0) && (a[j-1] > aux)){
      a[j] = a[j-1];
      j--;
    }
    a[j] = aux;
  }
}
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Ordenación de un vector por inserción}
\framesubtitle{Ejemplo de fuerza bruta}
\begin{itemize}
\item Este algoritmo divide el vector en dos partes, una con elementos ya ordenados y la otra con elementos todavía sin ordenar.

\item Inicialmente la parte ordenada está vacía y la que no está ordenada contiene todos los números.

\item El algoritmo utiliza la fuerza bruta para ir tomando uno por uno los elementos de la parte desordenada y los va insertado en la parte ordenada en el lugar que les corresponde.

\item Resulta sencillo comprobar que este algoritmo tiene un coste temporal $O(n^2)$.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Ejemplo de ordenación de un vector por inserción}
\framesubtitle{Ejemplo de fuerza bruta}
\begin{center}
\includegraphics[scale=0.5]{img/ordenacion_insercion.eps} 
\end{center}
\end{frame}
